/*
 * @lc app=leetcode.cn id=96 lang=cpp
 *
 * [96] 不同的二叉搜索树
 */

// @lc code=start
class Solution
{
public:
    int numTrees(int n)
    {
        //不同的二叉搜索树
        //dp[1]=1 dp[2]=2 需要画图来表示
        //分析到dp[3]的时候就比较明显了
        //分别有三种情况左子树有2元素 右子树0 左子树1右子树1 左子树0右子树2
        //分别对应dp[0] dp[1] dp[2]
        //也就说dp[3]=d[2]*d[0]+dp[1]*d[1]+dp[0]*dp[2]=5
        //所以递归方程就是需要加一个for循环
        //初始化需要将dp[0]=0
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};
// @lc code=end
